package fun.ticsmyc.question;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-25 17:22
 *
 *
 * 输入： 参数1，正数数组costs 参数2，正数数组profits 参数3，
 * 正数k 参数4，正数m
 * costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花
 * 费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多
 * 做k个项目 m表示你初始的资金
 * 说明：你每做完一个项目，马上获得的收益，可以支持你去做下
 * 一个 项目。
 * 输出： 你最后获得的最大钱数。
 */
public class 大小根堆贪心项目最大收益 {



    /**
     * 可以做的项目：根据利润维护大顶堆
     */
    PriorityQueue<Node> profitsHeap = new PriorityQueue<>(new MaxHeapComparator());
    /**
     * 还不能做的项目：根据成本维护小顶堆
     */
    PriorityQueue<Node> capitalHeap = new PriorityQueue<>(new MinHeapComparator());

    /**
     *
     * @param profits  项目i对应的利润
     * @param capital  项目i对应的成本
     * @param k        最多做k个项目
     * @param m        初始资金m
     * @return
     */
    public int findMaximizedCapital(int[] profits,int[] capital , int k ,int m){
        for(int i=0 ; i<profits.length; ++i){
            Node temp  = new Node(profits[i],capital[i]);
            //入堆
            if(temp.capital <= m){
                //入利润堆
                profitsHeap.offer(temp);
            }else{
                //入成本堆
                capitalHeap.offer(temp);
            }
        }

        int projectNum = 0;
        while(projectNum < k && !profitsHeap.isEmpty()){
            m += profitsHeap.poll().profit;
            projectNum++;
            while(!capitalHeap.isEmpty() && capitalHeap.peek().capital <=m){
                profitsHeap.offer(capitalHeap.poll());
            }
        }
        return m;
    }

    @Test
    public void test(){
        int[] profits= new int[]{3,5,3,2};
        int[] capital = new int[]{5,4,1,2};

        System.out.println(findMaximizedCapital(profits,capital,2,3));

    }

    static class Node{
        int profit;
        int capital;
        public Node(int profit,int capital){
            this.profit = profit;
            this.capital = capital;
        }
    }
    static class MinHeapComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.capital-o2.capital;
        }
    }
    static class MaxHeapComparator implements Comparator<Node>{

        @Override
        public int compare(Node o1, Node o2) {
            return o2.profit-o1.profit;
        }
    }

}
